package leetcode.daily;

import java.util.*;

/**
 * @author : zx
 * @version V1.0
 */
public class med_difficult_20201214 {

    /**
     * 1353. 最多可以参加的会议数目
     * 给你一个数组 events，其中 events[i] = [startDayi, endDayi] ，表示会议 i 开始于 startDayi ，结束于 endDayi 。
     *
     * 你可以在满足 startDayi <= d <= endDayi 中的任意一天 d 参加会议 i 。注意，一天只能参加一个会议。
     *
     * 请你返回你可以参加的 最大 会议数目。
     *
     *
     *
     * 示例 1：
     *
     *
     *
     * 输入：events = [[1,2],[2,3],[3,4]]
     * 输出：3
     * 解释：你可以参加所有的三个会议。
     * 安排会议的一种方案如上图。
     * 第 1 天参加第一个会议。
     * 第 2 天参加第二个会议。
     * 第 3 天参加第三个会议。
     * 示例 2：
     *
     * 输入：events= [[1,2],[2,3],[3,4],[1,2]]
     * 输出：4
     * 示例 3：
     *
     * 输入：events = [[1,4],[4,4],[2,2],[3,4],[1,1]]
     * 输出：4
     * 示例 4：
     *
     * 输入：events = [[1,100000]]
     * 输出：1
     * 示例 5：
     *
     * 输入：events = [[1,1],[1,2],[1,3],[1,4],[1,5],[1,6],[1,7]]
     * 输出：7
     *
     *
     * 提示：
     *
     * 1 <= events.length <= 10^5
     * events[i].length == 2
     * 1 <= events[i][0] <= events[i][1] <= 10^5
     *
     */
    public static int maxEvents(int[][] events) {
//        if(events == null || events.length == 0) return 0;
//        Map<Integer, List<Integer>> meets = new HashMap<>();
//        int start = Integer.MAX_VALUE, end = Integer.MIN_VALUE;
//        for(int i = 0; i < events.length; i++){
//            for(int d = events[i][0]; d <= events[i][1]; d++){
//                start = Math.min(start, d);
//                end = Math.max(end, d);
//                if(meets.containsKey(d)){
//                    meets.get(d).add(i);
//                }else{
//                    List<Integer> l = new ArrayList<>();
//                    l.add(i);
//                    meets.put(d, l);
//                }
//            }
//        }
//        boolean[] meeted = new boolean[events.length];
//        int nums = 0;
//        for (int d = start; d <= end; d++){
//            List<Integer> l = meets.get(d);
//            if(l != null){
//                int min = Integer.MAX_VALUE;
//                int elect = -1;
//                for (Integer i : l){
//                    if(!meeted[i]){
//                        if (events[i][1] - d < min){
//                            min = events[i][1] - d;
//                            elect = i;
//                        }
//                    }
//                }
//                if(elect >= 0){
//                    meeted[elect] = true;
//                    nums ++;
//                }
//            }
//        }
//        return nums;
        // 上面会超时
        Arrays.sort(events, new Comparator<int[]>(){
            @Override
            public int compare(int[] a, int[] b){
                return a[0] - b[0];
            }
        });
        PriorityQueue<Integer> queue = new PriorityQueue<>();
        int day = 0, id = 0, n = events.length, res = 0;
        while(id < n || !queue.isEmpty()){
            if(queue.isEmpty()){
                queue.add(events[id][1]);
                day = events[id++][0];
            }
            while(id < n && events[id][0] <= day){
                queue.add(events[id++][1]);
            }
            if(queue.peek() >= day){
                day++;
                res++;
            }
            queue.poll();
        }
        return res;
    }

    /**
     * 721. 账户合并
     * 给定一个列表 accounts，每个元素 accounts[i] 是一个字符串列表，其中第一个元素 accounts[i][0] 是 名称 (name)，其余元素是 emails 表示该帐户的邮箱地址。
     *
     * 现在，我们想合并这些帐户。如果两个帐户都有一些共同的邮件地址，则两个帐户必定属于同一个人。请注意，即使两个帐户具有相同的名称，它们也可能属于不同的人，因为人们可能具有相同的名称。一个人最初可以拥有任意数量的帐户，但其所有帐户都具有相同的名称。
     *
     * 合并帐户后，按以下格式返回帐户：每个帐户的第一个元素是名称，其余元素是按顺序排列的邮箱地址。accounts 本身可以以任意顺序返回。
     *
     * 例子 1:
     *
     * Input:
     * accounts = [["John", "johnsmith@mail.com", "john00@mail.com"], ["John", "johnnybravo@mail.com"], ["John", "johnsmith@mail.com", "john_newyork@mail.com"], ["Mary", "mary@mail.com"]]
     * Output: [["John", 'john00@mail.com', 'john_newyork@mail.com', 'johnsmith@mail.com'],  ["John", "johnnybravo@mail.com"], ["Mary", "mary@mail.com"]]
     * Explanation:
     *   第一个和第三个 John 是同一个人，因为他们有共同的电子邮件 "johnsmith@mail.com"。
     *   第二个 John 和 Mary 是不同的人，因为他们的电子邮件地址没有被其他帐户使用。
     *   我们可以以任何顺序返回这些列表，例如答案[['Mary'，'mary@mail.com']，['John'，'johnnybravo@mail.com']，
     *   ['John'，'john00@mail.com'，'john_newyork@mail.com'，'johnsmith@mail.com']]仍然会被接受。
     *
     * 注意：
     *
     * accounts的长度将在[1，1000]的范围内。
     * accounts[i]的长度将在[1，10]的范围内。
     * accounts[i][j]的长度将在[1，30]的范围内。
     *
     * 可以通过并查集优化
     */
    public List<List<String>> accountsMerge(List<List<String>> accounts) {
        HashMap<String, List<Account>> m = new HashMap<>();
        for(List<String> l : accounts){
            Account a = new Account(l);
            List<Account> al = m.get(a.name);
            if(al == null){
                al = new ArrayList<>();
                al.add(a);
                m.put(a.name, al);
            }else{
                boolean flag = false;
                Iterator<Account> i = al.listIterator();
                while (i.hasNext()){
                    Account it = i.next();
                    if(it.equals(a)){
                        if(flag){
                            a.add(it);
                            i.remove();
                        }else {
                            it.add(a);
                            a = it;
                            flag = true;
                        }
                    }
                }
                if(!flag) al.add(a);
            }
        }
        List<List<String>> res = new ArrayList<>();
        for(List<Account> i : m.values()){
            for(Account j : i){
                res.add(j.toList());
            }
        }
        return res;
    }

    private static class Account{
        String name;
        HashSet<String> set;

        Account(List<String> s){
            name = s.get(0);
            set = new HashSet<>();
            s.remove(0);
            set.addAll(s);
        }

        public boolean equals(Account a) {
            for(String i : a.set){
                if(set.contains(i)) return true;
            }
            return false;
        }

        public void add(Account a){
            set.addAll(a.set);
        }

        public List<String> toList(){
            List<String> l = new ArrayList<>();
            l.add(name);
            String[] a = (String[]) set.toArray(new String[0]);
            Arrays.sort(a);
            l.addAll(Arrays.asList(a));
            return l;
        }
    }

    /**
     * 1653. 使字符串平衡的最少删除次数
     * 给你一个字符串 s ，它仅包含字符 'a' 和 'b'​​​​ 。
     *
     * 你可以删除 s 中任意数目的字符，使得 s 平衡 。我们称 s 平衡的 当不存在下标对 (i,j) 满足 i < j 且 s[i] = 'b' 同时 s[j]= 'a' 。
     *
     * 请你返回使 s 平衡 的 最少 删除次数。
     *
     *
     *
     * 示例 1：
     *
     * 输入：s = "aababbab"
     * 输出：2
     * 解释：你可以选择以下任意一种方案：
     * 下标从 0 开始，删除第 2 和第 6 个字符（"aababbab" -> "aaabbb"），
     * 下标从 0 开始，删除第 3 和第 6 个字符（"aababbab" -> "aabbbb"）。
     * 示例 2：
     *
     * 输入：s = "bbaaaaabb"
     * 输出：2
     * 解释：唯一的最优解是删除最前面两个字符。
     *
     *
     * 提示：
     *
     * 1 <= s.length <= 105
     * s[i] 要么是 'a' 要么是 'b'​ 。​
     * @param s
     * @return
     */
    public static int minimumDeletions(String s) {
//        if(s == null || s.length() == 0) return -1;
//        if(s.length() == 1) return 0;
//        char[] sc = s.toCharArray();
//        return recursive('0', sc, 0);
        // 递归超时 使用dp

        char[] sc = s.toCharArray();
        // dp 0 以a结尾的平衡字符串裁剪次数 1 b  为空的时候不考虑既可以为a也可以为b
        int dp_i_0 = sc[0] == 'a' ? 0 : 1;
        int dp_i_1 = sc[0] == 'b' ? 0 : 1;
        for(int i = 1; i < s.length(); i++){
            if(sc[i] == 'a'){
                dp_i_0 = dp_i_0;
                dp_i_1 = dp_i_1 + 1;
            }else{
                dp_i_0 = dp_i_0 + 1;
                dp_i_1 = Math.min(dp_i_1, dp_i_0-1);
            }
        }
        return Math.min(dp_i_0, dp_i_1);
    }

    /**
     * 递归的方法 超时
     * @return
     */
    private static int recursive(char pre,char[] sc, int index){
        if(index >= sc.length) return 0;
        if(pre == 'a'){
            if(sc[index] == 'a') return recursive('a', sc, index+1);
            else return Math.min(
                    1+recursive('a', sc, index+1),
                    recursive('b', sc, index+1)
            );
        }else if(pre == 'b'){
            if(sc[index] == 'a') return 1+recursive('b', sc, index+1);
            else return recursive('b', sc, index+1);
        }else{
            return Math.min(
                    1+recursive('0', sc, index+1),
                    recursive(sc[index], sc, index+1)
            );
        }
    }

    /**
     * 1235. 规划兼职工作
     * 你打算利用空闲时间来做兼职工作赚些零花钱。
     *
     * 这里有 n 份兼职工作，每份工作预计从 startTime[i] 开始到 endTime[i] 结束，报酬为 profit[i]。
     *
     * 给你一份兼职工作表，包含开始时间 startTime，结束时间 endTime 和预计报酬 profit 三个数组，请你计算并返回可以获得的最大报酬。
     *
     * 注意，时间上出现重叠的 2 份工作不能同时进行。
     *
     * 如果你选择的工作在时间 X 结束，那么你可以立刻进行在时间 X 开始的下一份工作。
     *
     *
     *
     * 示例 1：
     *
     *
     *
     * 输入：startTime = [1,2,3,3], endTime = [3,4,5,6], profit = [50,10,40,70]
     * 输出：120
     * 解释：
     * 我们选出第 1 份和第 4 份工作，
     * 时间范围是 [1-3]+[3-6]，共获得报酬 120 = 50 + 70。
     * 示例 2：
     *
     *
     *
     * 输入：startTime = [1,2,3,4,6], endTime = [3,5,10,6,9], profit = [20,20,100,70,60]
     * 输出：150
     * 解释：
     * 我们选择第 1，4，5 份工作。
     * 共获得报酬 150 = 20 + 70 + 60。
     * 示例 3：
     *
     *
     *
     * 输入：startTime = [1,1,1], endTime = [2,3,4], profit = [5,6,4]
     * 输出：6
     *
     *
     * 提示：
     *
     * 1 <= startTime.length == endTime.length == profit.length <= 5 * 10^4
     * 1 <= startTime[i] < endTime[i] <= 10^9
     * 1 <= profit[i] <= 10^4
     * @param startTime
     * @param endTime
     * @param profit
     * @return
     */
    public static int jobScheduling(int[] startTime, int[] endTime, int[] profit) {
        int len = startTime.length;
        int[] dp = new int[len+1];
        Job[] jobs = new Job[len];
        for(int i = 0; i < len; i++){
            jobs[i] = new Job(startTime[i], endTime[i], profit[i]);
        }
        Arrays.sort(jobs, (o1,o2)->{return o1.end-o2.end;});
        for(int i = 1; i < dp.length; i++){
            // 不做工
            dp[i] = Math.max(dp[i-1], jobs[i-1].profit);
            for(int j = i-1; j > 0; j--){
                if(jobs[j-1].end <= jobs[i-1].start){
                    dp[i] = Math.max(dp[i], dp[j]+jobs[i-1].profit);
                    break;
                }
            }
        }
        return dp[len];
    }

    private static class Job{
        int start, end, profit;
        Job(int start, int end, int profit){
            this.start = start;
            this.end = end;
            this.profit = profit;
        }
    }

    /**
     * 871. 最低加油次数
     * 汽车从起点出发驶向目的地，该目的地位于出发位置东面 target 英里处。
     *
     * 沿途有加油站，每个 station[i] 代表一个加油站，它位于出发位置东面 station[i][0] 英里处，并且有 station[i][1] 升汽油。
     *
     * 假设汽车油箱的容量是无限的，其中最初有 startFuel 升燃料。它每行驶 1 英里就会用掉 1 升汽油。
     *
     * 当汽车到达加油站时，它可能停下来加油，将所有汽油从加油站转移到汽车中。
     *
     * 为了到达目的地，汽车所必要的最低加油次数是多少？如果无法到达目的地，则返回 -1 。
     *
     * 注意：如果汽车到达加油站时剩余燃料为 0，它仍然可以在那里加油。如果汽车到达目的地时剩余燃料为 0，仍然认为它已经到达目的地。
     *
     *
     *
     * 示例 1：
     *
     * 输入：target = 1, startFuel = 1, stations = []
     * 输出：0
     * 解释：我们可以在不加油的情况下到达目的地。
     * 示例 2：
     *
     * 输入：target = 100, startFuel = 1, stations = [[10,100]]
     * 输出：-1
     * 解释：我们无法抵达目的地，甚至无法到达第一个加油站。
     * 示例 3：
     *
     * 输入：target = 100, startFuel = 10, stations = [[10,60],[20,30],[30,30],[60,40]]
     * 输出：2
     * 解释：
     * 我们出发时有 10 升燃料。
     * 我们开车来到距起点 10 英里处的加油站，消耗 10 升燃料。将汽油从 0 升加到 60 升。
     * 然后，我们从 10 英里处的加油站开到 60 英里处的加油站（消耗 50 升燃料），
     * 并将汽油从 10 升加到 50 升。然后我们开车抵达目的地。
     * 我们沿途在1两个加油站停靠，所以返回 2 。
     *
     *
     * 提示：
     *
     * 1 <= target, startFuel, stations[i][1] <= 10^9
     * 0 <= stations.length <= 500
     * 0 < stations[0][0] < stations[1][0] < ... < stations[stations.length-1][0] < target
     * @param target
     * @param startFuel
     * @param stations
     * @return
     */
    public int minRefuelStops(int target, int startFuel, int[][] stations) {
        int n = stations.length;
        // dp[i][j]表示经过i站加油j次能够到达的最远距离
        int[][] dp = new int[n + 1][n + 1];

        if (startFuel >= target)
            return 0;
        for (int i = 0; i < n; i++)
            dp[i][0] = startFuel;

        for (int i = 1; i <= n; i++) {
            int currStationPos = stations[i - 1][0];
            int currStationGas = stations[i - 1][1];
            for (int j = 1; j <= i; j++) {
                // 因为dp[i][j]表示经过前i站，一共加油j次。要么第i站加油，1~i-1站加j-1次；要么第i站不加油，前面1~i-1加j次
                // 前i-1站加j次，本站不加油
                if (dp[i - 1][j] >= currStationPos) {
                    dp[i][j] = dp[i - 1][j];
                }
                // max(前i-1站加j次，本站不加油, 前i-1站加j-1次，本站加油)
                if (dp[i - 1][j - 1] >= currStationPos) {
                    dp[i][j] = Math.max(dp[i][j], dp[i - 1][j - 1] + currStationGas);
                }
            }
        }

        // 此时走完了n站，看看最少加油几次能达到target
        for (int refuelTimes = 0; refuelTimes <= n; refuelTimes++)
            if (dp[n][refuelTimes] >= target)
                return refuelTimes;
        return -1;
    }


    public static void main(String args[]){
//        System.out.println(maxEvents(new int[][]{
//                new int[]{1,4},
//                new int[]{4,4},
//                new int[]{2,2},
//                new int[]{3,4},
//                new int[]{1,1},
//        }));
//        System.out.println(minimumDeletions("aababbab"));
        System.out.println(jobScheduling(new int[]{1,2,3,3},
                new int[]{3,4,5,6},
                new int[]{50,10,40,70}));
    }
}
